package com.xing.algorithm.linkedlist;

public class ReverseBetweenLinkedList {
    public static ListNode reverseBetween(ListNode head, int m, int n) {
        if(head == null || head.next == null || m == n || m >= n) {
            return head;
        }

        ListNode dummy = new ListNode(0);
        dummy.next = head;

        int count = 1;
        ListNode pre = null;
        ListNode p = head;
        while(count < m) {
            pre = p;
            p = p.next;
            count ++;
        }

        ListNode cur = p;
        while(count <= n) {
            cur = cur.next;
            count ++;
        }

        if(pre == null) {
            head = reverseListNode(p,cur);
            p.next = cur;
            return head;
        }else {
            pre.next = reverseListNode(p, cur);
            p.next = cur;
        }

        return dummy.next;

    }

    private static ListNode reverseListNode(ListNode start, ListNode end) {
        ListNode newh = null;
        while(start !=  end) {
            ListNode tmp = start.next;
            start.next = newh;
            newh = start;
            start = tmp;
        }
        return newh;
    }
    public static void main(String[] args) {
        ListNode root = new ListNode(1);
        ListNode next1 = new ListNode(2);
//        ListNode next2 = new ListNode(3);
//        ListNode next3 = new ListNode(4);
//        ListNode next4 = new ListNode(5);

        root.next = next1;
//        next1.next = next2;
//        next2.next = next3;
//        next3.next = next4;

        ListNode newh = reverseBetween(root, 1 ,2);

        StringBuilder sb = new StringBuilder();
        while(newh != null) {
            sb.append(newh.val).append("->");
            newh = newh.next;
        }

        System.out.println(sb.toString());

    }

    static class ListNode {
        public int val;
        public ListNode next;
        public ListNode(int val) {
            this.val = val;
        }
    }
}
